#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <unordered_map>
#include <vector>

// 包含搜索算法的头文件
#include "linear_search.h"
#include "binary_search.h"
#include "hash_search.h"

// 用于生成随机数组的函数
void generateRandomArray(int arr[], int n, int maxVal = 10000) {
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % maxVal;
    }
}

// 用于复制数组的函数
void copyArray(const int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试搜索算法性能的函数
template<typename T>
void testSearchFunction(T searchFunc, const char* name, int arr[], int n, int x) {
    int tempArr[n];
    copyArray(arr, tempArr, n);

    clock_t start, end;
    double cpu_time_used;

    start = clock();
    for (int  i = 0; i < 100000; i++)
    {
            int z = searchFunc(tempArr, n, x);
    }
    
    int result = searchFunc(tempArr, n, x);
    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    std::cout << name << " took " << cpu_time_used << " seconds to search 100000 times for " << x << ". Result: " << result << std::endl;
}

template<typename T>
void testSearchFunction(T searchFunc, const char* name, int arr[], int l,int r, int x) {
    int tempArr[x];
    copyArray(arr, tempArr, x);

    clock_t start, end;
    double cpu_time_used;

    start = clock();
    for(int i=0; i<100000;i++){
        int c = searchFunc(tempArr, l,r,x);
    }
    int result =searchFunc(tempArr, l,r,x);
    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    std::cout << name << " took " << cpu_time_used << " seconds to search  100000 times for " << x << ". Result: " << result << std::endl;
}
// 用于二分搜索的有序数组生成函数
void generateSortedArray(int arr[], int n, int maxVal = 10000) {
    for (int i = 0; i < n; i++) {
        arr[i] = i % maxVal;
    }
    std::sort(arr, arr + n);
}

int main() {
    srand(time(0)); // 初始化随机数种子
    const int SIZE = 100000; // 数组大小
    int arr[SIZE];
    int sortedArr[SIZE];
    int target = 50000; // 搜索的目标值

    generateRandomArray(arr, SIZE);
    generateSortedArray(sortedArr, SIZE);

    // 测试线性搜索
    testSearchFunction(linearSearch, "Linear Search", arr, SIZE, target);

    // 测试二分搜索
    testSearchFunction(binarySearch, "Binary Search", sortedArr, 0, SIZE - 1, target);

    // 测试哈希查找
    std::unordered_map<int, int> hashTable;
    for (int i = 0; i < SIZE; ++i) {
        hashTable[arr[i]] = i;
    }

    clock_t start, end;
    double cpu_time_used;

    start = clock();
    for(int i =0;i<100000;i++){
        int c = hashSearch(hashTable, target);
    }
    int result = hashSearch(hashTable, target);
    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    std::cout << "Hash Search took " << cpu_time_used << " seconds to search 100000 times for " << target << ". Result: " << result << std::endl;

    return 0;
}